In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, .
Characterization
The
Schlegel diagram of a convex polyhedron represents its vertices and edges as points and line segments in the
Euclidean plane, forming a subdivision of an outer
convex polygon into smaller convex polygons (a
convex drawing of the graph of the polyhedron). It has no crossings, so every polyhedral graph is also a
planar graph. Additionally, by Balinski's theorem, it is a 3-vertex-connected graph.
According to Steinitz's theorem, these two graph-theoretic properties are enough to completely characterize the polyhedral graphs: they are exactly the 3-vertex-connected planar graphs. That is, whenever a graph is both planar and 3-vertex-connected, there exists a polyhedron whose vertices and edges form an isomorphic graph.[.] Given such a graph, a representation of it as a subdivision of a convex polygon into smaller convex polygons may be found using the Tutte embedding.[.]
Hamiltonicity and shortness
Tait conjectured that every
cubic graph polyhedral graph (that is, a polyhedral graph in which each vertex is incident to exactly three edges) has a Hamiltonian cycle, but this conjecture was disproved by a
counterexample of W. T. Tutte, the polyhedral but non-Hamiltonian
Tutte graph. If one relaxes the requirement that the graph be cubic, there are much smaller non-Hamiltonian polyhedral graphs. The graph with the fewest vertices and edges is the 11-vertex and 18-edge
Herschel graph,
and there also exists an 11-vertex non-Hamiltonian polyhedral graph in which all faces are triangles, the Goldner–Harary graph.
More strongly, there exists a constant (the shortness exponent) and an infinite family of polyhedral graphs such that the length of the longest simple path of an -vertex graph in the family is .
A problem with one additional constraint exists, Barnette's conjecture, asking whether every cubic bipartite graph polyhedral graph is Hamiltonian, which remains unsolved.
Combinatorial enumeration
Duijvestijn provides a count of the polyhedral graphs with up to 26 edges;
[.] The number of these graphs with 6, 7, 8, ... edges is
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... .
One may also enumerate the polyhedral graphs by their numbers of vertices: for graphs with 4, 5, 6, ... vertices, the number of polyhedral graphs is
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... .
Special cases
The graphs of the
have been called
Platonic graphs. As well as having all the other properties of polyhedral graphs, these are
, and all of them have Hamiltonian cycles.
There are five of these graphs:
-
Tetrahedral graph – 4 vertices, 6 edges
-
Octahedral graph – 6 vertices, 12 edges
-
Cubical graph – 8 vertices, 12 edges
-
Icosahedral graph – 12 vertices, 30 edges
-
Dodecahedral graph – 20 vertices, 30 edges
A polyhedral graph is the graph of a simple polyhedron if it is cubic graph (every vertex has three edges), and it is the graph of a simplicial polyhedron if it is a maximal planar graph. For example, the tetrahedral, cubical, and dodecahedral graphs are simple; the tetrahedral, octahedral, and icosahedral graphs are simplicial.
The , graphs formed from a planar embedded tree by adding an outer cycle connecting all of the leaves of the tree, form another important subclass of the polyhedral graphs.
See also
External links
